// https://leetcode.cn/problems/ransom-note/
package leet308ransomnote

// 思路：
// 1. 定义一个哈希表，用于存储杂志中每个字符的出现次数
// 2. 遍历杂志字符串，将每个字符的出现次数存入哈希表
// 3. 遍历赎金信字符串，检查每个字符在哈希表中的出现次数是否足够
// 4. 如果某个字符在哈希表中的出现次数不足，返回false
// 5. 如果所有字符在哈希表中的出现次数都足够，返回true
// 6. 时间复杂度O(m+n)，空间复杂度O(1)
// 7. 注意：
// 8. 这里的m和n分别是杂志字符串和赎金信字符串的长度
// 9. 这里的哈希表使用的是一个长度为26的数组，
// 10. 用于存储每个字符的出现次数
// 11. 这里的字符范围是小写字母a-z，所以数组的长度为26
// 12. 如果字符范围是其他字符，可以使用哈希表来存储

func canConstruct(ransomNote string, magazine string) bool {
	// 定义一个长度为26的数组，用于存储每个字符的出现次数
	// 这里的字符范围是小写字母a-z，所以数组的长度为26
	// 如果字符范围是其他字符，可以使用哈希表来存储
	count := [26]int{}
	// 遍历杂志字符串，将每个字符的出现次数存入哈希表
	// 字符减去a的差值代替具体的字符，字符本质上就是个数字
	for _, c := range magazine {
		count[c-'a']++
	}
	// 遍历赎金信字符串，检查每个字符在哈希表中的出现次数是否足够
	for _, c := range ransomNote {
		// 从哈希表中找到当前字符减去一个库存，如果库存小于0说明无法拼凑出来。
		count[c-'a']--
		if count[c-'a'] < 0 {
			return false
		}
	}
	return true
}